/***************************************************
 * @Author: OBKoro1
 * @Create: 2021-02-21
 * @LastEditors: OBKoro1
 * @LastEditTime: 2021-02-21
 * @FilePath: \leetcode-exercise\137-地下城游戏\test.c
 ****************************************************/
#define N 150
int map[N][N];

int min(int a, int b)
{
    return (a < b) ? a : b;
}

int max(int a, int b)
{
    return (a > b) ? a : b;
}

int DFS(int **dungeon, int max_row, int max_col, int row, int col)
{
    int res;
    // 到达右下方底部
    if (col == (max_col - 1) && row == (max_row - 1))
    {
        // 血量最低不能小于1个
        return max(1 - dungeon[row][col], 1);
    }
    // 记忆优化，可删除对比优化
    if (map[row][col] > 0)
    {
        return map[row][col];
    }

    if (col == (max_col - 1))
    {
        // 最右侧，只能往下走
        res = max(DFS(dungeon, max_row, max_col, row + 1, col) - dungeon[row][col], 1);
    }
    else if (row == (max_row - 1))
    {
        // 底层，只能向右走
        res = max(DFS(dungeon, max_row, max_col, row, col + 1) - dungeon[row][col], 1);
    }
    else
    {
        // 左右都能走，取最小的耗血方向前进
        res = max(min(DFS(dungeon, max_row, max_col, row + 1, col), DFS(dungeon, max_row, max_col, row, col + 1)) - dungeon[row][col], 1);
    }
    // 记忆分支记录结果，到当前点最小的耗血值记录， 可删除对比
    map[row][col] = res;
    return res;
}

int calculateMinimumHP(int **dungeon, int dungeonSize, int *dungeonColSize)
{
    int res = -1;
    if (dungeon == NULL || dungeonSize == 0 || dungeonColSize == NULL)
    {
        return res;
    }
    int row = dungeonSize;
    int col = *dungeonColSize;
    memset(map, 0, sizeof(map));
    res = DFS(dungeon, row, col, 0, 0);
    return res;
}